class Solution
{
public:
    int findCrossingTime(int n, int k, vector<vector<int>> &time)
    {
        auto compareEfficiency = [&](int i, int j)
        {
            int iTime = time[i][0] + time[i][2];
            int jTime = time[j][0] + time[j][2];
            if (iTime == jTime)
            {
                return i < j;
            }
            return iTime < jTime;
        };

        priority_queue<int, vector<int>, decltype(compareEfficiency)> leftWorkers(compareEfficiency);
        priority_queue<int, vector<int>, decltype(compareEfficiency)> rightWorkers(compareEfficiency);
        for (int i = 0; i < k; ++i)
        {
            leftWorkers.push(i);
        }

        enum
        {
            ArriveRight,
            ArriveLeft,
            PickOldFinish,
            PutNewFinish
        };

        auto compareEndTime = [](auto &e1, auto e2)
        {
            return e1[0] > e2[0];
        };

        int curTime = 0;
        int boxRemain = n;
        int lastArrive = 0;
        bool bridgeOccupied = false;
        priority_queue<vector<int>, vector<vector<int>>, decltype(compareEndTime)> events(compareEndTime);

        while (true)
        {
            if (!events.empty())
            {
                auto event = events.top();
                events.pop();
                curTime = event[0];
                int worker = event[2];
                switch (event[1])
                {
                case ArriveLeft:
                {
                    lastArrive = curTime;
                    events.push({curTime + time[worker][3], PutNewFinish, worker});
                    bridgeOccupied = false;
                    break;
                }
                case ArriveRight:
                {
                    events.push({curTime + time[worker][1], PickOldFinish, worker});
                    bridgeOccupied = false;
                    break;
                }
                case PickOldFinish:
                {
                    rightWorkers.push(worker);
                    break;
                }
                case PutNewFinish:
                {
                    leftWorkers.push(worker);
                    break;
                }
                default:
                    break;
                }
            }
            if (!bridgeOccupied && !rightWorkers.empty())
            {
                int rightWorker = rightWorkers.top();
                rightWorkers.pop();
                bridgeOccupied = true;
                events.push({curTime + time[rightWorker][2], ArriveLeft, rightWorker});
            }
            else if (!bridgeOccupied && boxRemain && !leftWorkers.empty())
            {
                int leftWorker = leftWorkers.top();
                leftWorkers.pop();
                bridgeOccupied = true;
                events.push({curTime + time[leftWorker][0], ArriveRight, leftWorker});
                --boxRemain;
            }
            if (boxRemain == 0 && events.empty())
            {
                break;
            }
        }
        return lastArrive;
    }
};